package kyssion.leetcode.num51_100;

public class code62_不同路径 {
    public static void main(String[] args) {
        System.out.println(new code62_不同路径().uniquePaths(7,3));
    }
    public int uniquePaths(int m, int n) {
        if(m==0||n==0){
            return 0;
        }
        int[] dp = new int[m];
        for (int a = 0; a < dp.length; a++) {
            dp[a] = 1;
        }
        for (int a = 1; a < n; a++) {
            for (int b = 1; b < dp.length; b++) {
                dp[b] = dp[b - 1] + dp[b];
            }
        }
        return dp[m - 1];
    }

    /**
     * 公式法
     * @param m
     * @param n
     * @return
     */
    int uniquePaths2(int m, int n) {
        int total = m + n -2; //一共要走的步数
        int down = m - 1;  //向下要走的步数
        double res = 1;
        for(int i = 1 ; i <= down; i++){
            res =res * (total - down + i) / i;
        }
        return (int)res;
    }
}
